package com.it;

public class DoubleLinkedList<E> {
    protected static final class Node<E> {
        private Node<E> pre;
        private Node<E> next;
        private E data;

        public Node() {

        }

        public Node(E data, Node<E> pre, Node<E> next) {
            this.data = data;
            this.next = next;
            this.pre = pre;
        }

        public void setData(E data) {
            this.data = data;
        }

        public E getData() {
            return data;
        }

        public void setNext(Node<E> next) {
            this.next = next;
        }

        public Node<E> getNext() {
            return next;
        }

        public void setPre(Node<E> pre) {
            this.pre = pre;
        }

        public Node<E> getPre() {
            return pre;
        }

    }

    public Node<E> head;
    public int size;

    public DoubleLinkedList() {
        head = new Node<>();
        size = 0;
    }

    public DoubleLinkedList(E data) {
        head.data = data;
        size = 0;
    }

    // 添加数据
    public boolean add(E data) {

        if (head.getNext() == null) {
            Node<E> newNode = new Node<E>(data, head, null);
            head.setNext(newNode);
            head.setPre(newNode);
        } else {
            Node<E> newNode = new Node<E>(data, head.getPre(), null);
            head.getPre().setNext(newNode);
            head.setPre(newNode);
        }
        size++;
        return true;
    }

    // 正序打印数据
    public void postivePrint() {
        if (this.head.getNext() == null) {
            return;
        }
        Node<E> cur = this.head.getNext();
        for (int i = 0; i < this.size; i++) {
            System.out.println(cur.getData());
            cur = cur.getNext();
        }
    }

    // 倒序打印数据
    public void negativePrint() {
        if (this.head.getNext() == null) {
            return;
        }
        Node<E> cur = head.getPre();
        while (cur != head) {
            System.out.println(cur.getData());
            cur = cur.getPre();
        }
    }

    // 创建一个节点
    public Node<E> createNode(E data, Node<E> pre, Node<E> next) {
        return new Node<E>(data, pre, next);
    }

    // 删除节点
    // 1.根据索引删除从0开始
    public E indexRemove(int index) {
        Node<E> cur = head.getNext();
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        Node<E> pre = cur.getPre();
        Node<E> next = cur.getNext();
        // 开始删除
        // 判断是不是尾删
        if (cur == head.getPre()) {
            return endRemove();
        } else {
            pre.setNext(next);
            next.setPre(pre);
            cur.setNext(null);
            cur.setPre(null);
            size--;
        }
        return cur.getData();
    }

    // 2.根据数值删除
    public boolean remove(E data) {
        if (contain(data) < 0) {
            return false;
        } else {
            indexRemove(contain(data));
            return true;
        }
    }

    // 判断是否存在
    public int contain(E data) {
        Node<E> cur = head.next;
        for (int i = 0; i < size; i++) {
            if (cur.getData() == data) {
                return i;
            }
            cur = cur.next;
        }
        return -1;
    }

    // 尾删
    public E endRemove() {
        Node<E> end = head.getPre();
        Node<E> pre = end.getPre();
        end.setPre(null);
        head.setPre(pre);
        pre.setNext(null);
        size--;
        return end.getData();
    }

    // 头删
    public E fristRemove() {
        return indexRemove(0);
    }

    // 返回长度
    public int lenth() {
        return this.size;
    }

    // 插入
    public boolean insertByIndex(E data, int index, Boolean model) {
        // model为true是前插,model为false是后插
        if (index >= size || index < 0) {
            return false;
        }
        // 获取节点
        Node<E> cur = head.next;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        Node<E> pre = cur.getPre();
        Node<E> next = cur.getNext();
        // 开始插入
        if (model) {
            Node<E> newNode = createNode(data, pre, cur);
            pre.setNext(newNode);
            cur.setPre(newNode);
        } else {
            if (cur == head.getPre()) {
                // Node<E> newNode=createNode(data,cur, null);
                // pre.setNext(newNode);
                // head.setPre(newNode);
                this.add(data);
                size--;
            } else {
                Node<E> newNode = createNode(data, cur, next);
                pre.setNext(newNode);
                next.setPre(newNode);
            }
        }
        size++;
        return true;
    }

    // 头插
    public boolean firstInsert(E data) {
        return insertByIndex(data, 0, true);
    }

    // 尾插
    public boolean endInsert(E data) {
        return insertByIndex(data, size - 1, true);
    }

    // 清除空间
    public boolean clear() {
        int n = this.size;
        for (int i = 0; i < n; i++) {
            endRemove();
        }
        return true;
    }
}


